
/*
 * Given n non-negative integers representing an 
 * elevation map where the width of each bar is 1, 
 * compute how much water it is able to trap after raining.

My solution:
divide and conquer, divide the field into multiple pieces

 */

public class TrappingRainWater {
	public void tester() {
		int [] a = new int [10000000];
		
		for(int i = 0 ; i < a.length ; i++) {
			a[i] = (int) (Math.random()*1000);
//			System.out.println(a[i]);
		}
		
		System.out.println(trap2(a));
	}
	
	public int trap(int[] A) {
	    if (A.length < 3) return 0;

	    int ans = 0;
	    int l = 0, r = A.length - 1;

	    // find the left and right edge which can hold water
	    while (l < r && A[l] <= A[l + 1]) l++;
	    while (l < r && A[r] <= A[r - 1]) r--;
	    
//	    System.out.println("l: "+l+" r: "+r);

	    while (l < r) {
	        int left = A[l];
	        int right = A[r];
	        if (left <= right) {
	            // add volum until an edge larger than the left edge
	            while (l < r && left >= A[++l]) {
	                ans += left - A[l];
	            }
	        } else {
	            // add volum until an edge larger than the right volum
	            while (l < r && A[--r] <= right) {
	                ans += right - A[r];
	            }
	        }
	    }
	    return ans;
	}
	
    public int trap2(int[] A) {
        return d(A, 0, A.length-1);
    }
    
    public int d(int[] A, int a, int b) {
    	for(int i = a+1 ; i < b ; i++) {
    		if(A[i] >= A[a]) {
//    			System.out.println(a+" "+b+ " "+i);
    			return d(A,a,i)+d(A,i,b);
    		}
    	}
    	for(int i = b-1 ; i > a ; i--) {
    		if(A[i] >= A[b]) {
    			return d(A, a, i) + d(A, i, b);
    		}
    	}
    	
    	if(a >= b-1) return 0;
    	
//    	System.out.println(a+" "+b+" "+getArea(A, a, b));
    	return getArea(A, a, b);
    }
    
    public int getArea(int [] c, int a, int b) {
    	int min = 0;
    	if(c[a] > c[b]) min = c[b];
    	else min = c[a];
    	
    	int sum = 0;
    	
    	for(int i = a+1; i < b ; i++) {
    		sum = sum + min - c[i];
    	}
    	
    	return sum;
    }
}